That is not accurate.
The normal force can exist even if the surface is not horizontal (or the floor). A ball rolling down a ramp still experiences a normal force that is perpendicular to the slope of the ramp.
Normal force can also exist on a curve. A ball rolling in a halfpipe experiences a normal force that is always pointed towards the center of the circle. (also motorcycle cage of death)
Normal force can even exist without gravity. Spinning Spaceship that simulates gravity from centrifugal effects would cause you to experiences a normal force towards the center of rotation. (
http://en.wikipedia.org/wiki/Rotating_wheel_space_station)
The normal force just prevents solid bodies from moving through each other.