There are a few different ways.
First way is to embed your view controller in Navigation controller instead of adding navigation bar directly to your view controller. Select your view controller and select Editor->Embed in->Navigation controller. It will add a navigation controller to the storyboard and will set up your view controller as its root controller. This will work even if you use Tableview Controller (which won't let you add navigation bar manually in interface builder). I would recommend you to use this way.
See screenshot http://imgur.com/WQhgktf
Second way is to add navigation bar directly to the controller and to check the hierarchy of the views: both table view and navigation bar should be on the same level and navigation bar should follow table view. Most likely your navigation bar was added as a subview of the table view. Note that I would not recommend you to follow this way, because you will have to manually add constraints, this method won't work with table view controller, plus you can run in some other problems.
See screenshot http://imgur.com/UYeq8vF