The contacts app is in a folder by default on a brand new iPhone. You might need to look in the folder to find it. If you want to move the icon out of the folder follow these steps:
1. Open the folder
2. Long tap on the Contacts icon until the icon starts to wiggle.
3. Tap the icon and drag the icon to another area of the home screen to move it out of the folder.