You're skipping about 1000 years of history there to make your point. By the time of the rise of nationalism, many parts of Europe had shifted back and forth in control between larger empires for hundreds of years, and it mostly was not a continent of tiny little city states and small kingdoms any longer. The era of the city states started fading quickly after the renaissance, and were in the first place mostly limited to small parts of Europe - most of Europe had seen ongoing consolidation of smaller kingdoms for a millennia or two by the time nationalism became a factor.
See this map from 1713, for example: http://victoriavane.files.wordpress.com/2011/08/western_euro...
Even of the smaller states, many were parts of larger empires for most of their existence, though the control might shift back and forth between empires.
E.g. Germany did not exist as a united country, sure, but the Holy Roman Empire (not to be confused with the Roman Empire) encompassed most of the smaller countries on the territories of present day Germany and at various times part of Italy, Belgium, Netherlands, Austria, France, Switzerland, Poland, Croatia, Slovenia, Czech Republic. Even within the Holy Roman Empire, many of the constituent states were at various times larger than their succeeding present day European states (though there were also many smaller states).
Nationalism in many instances erected substantial new borders in Europe in places where borders meant little to ordinary people before.