In my opinion this is a question to which it is rather impossible to give a straight answer, since we cannot even begin to debate whether there were nation-states, or the concept of them, before any given date, until we agree on what a nation-state is, and that turns out to be rather difficult.

State is relative easy I think; even though Wikipedia cautions "there is no undisputed definition of a state", its first sentence ("A state is a centralized political organization that imposes and enforces rules over a population within a territory.") seems pretty reasonable, and for the sake of this post let's hand-wave a little bit and pretend everybody basically knows and agrees what a state is, even if they argue over the finer details or how to express it.

Nation on the other hand is extremely difficult to define in any sort of consistent, specific fashion. Clearly, since we have the term nation-state, it must be different from a state; we must be able to have nations that do not have states and states that are not nations. When challenged to define a nation, without tautologically using the borders or citizenship of nation-states to do so, people (not historians specifically, but people in general) will most often turn to factors like language, religion and ethnicity. However with all of these it is trivially easy to think of counterexamples.

If a nation is a group of people sharing a language, then what do we make of places like Switzerland? Perhaps you are happy to say "right, its not a nation-state, it's a confederation". But then look at Italy, pre-unification 'Italians' spoke many languages/dialects (again - infinite room for arguing semantics here) of varying mutual intelligibility. Look at France, one of many examples where the use of a single standard national language was (and is) something that had to be imposed by the state, often forcefully/controversially, rather than a unified linguistic community voluntarily forming the basis for the (nation)-state. And conversely you can point to people speaking the same language but identifying as different nationalities.

You can repeat this awkward-counterexample-finding exercise for religion and ethnicity, and so far I've only been looking at Europe to do so - but it's even more obvious when looking at the New World, or almost any country in post-colonial Africa, that the idea of a direct 1:1 correspondence between ethno-linguistic-religious groups and nations, is hopelessly flawed. You therefore resort to even vaguer terms like shared "culture" or "history", which are even more liable to dispute.

But in a way this "it's none of those things, but also all of those things" problem with defining the basis for nations, isn't so much us failing to find a definition, as discovering it. That is, you could argue, the concept of a "nation" is invented precisely at the point where it is required: at the point where existing identities and categories of identities are becoming inadequate. At a point where there are groups of people starting to form identities which are across a territory bigger than a single city or comparable small region, identities which are based on some extensively-overlapping-but-not-necessarily-exclusively-or-universally-shared aspects of ethnicity, language, religion, culture, etc.

Benedict Anderson coined the term "imagined communities" to describe this, because unlike traditional 'communities' like medieval villages they were far too big for you to literally know or interact with all the members, yet people were imagining themselves as members all the same (and/or, elites were telling them that they should).

If we need this new form of "national" identity, that implies we have new forms of social organisation, which implies that nations and nationalism are a historical phenomenon born from changing conditions, as opposed to some eternal, inherent thing. Which (finally!) gets us somewhere back towards your original question, when they arose.

If I were to try and answer your question as concisely as possible I would say that broadly, historians do consider the modern concept of the nation-state to have emerged rather than being eternal, but your 1800s mark is a little on the late side. Many historians link nations/nationalism to the emergence of 'modernity', in various different ways, and so you could take various different dates from them, but I think they all lean towards at least slightly earlier than 1800.

In the aforementioned Imagined Communities (1982), Anderson specifically highlights the emergence of 'print capitalism' as a key enabler for nationalism, since the printing press technology and resulting rise in mass literacy were requirements for forming these type of 'bigger than traditionally physically possible' communities. Gutenberg kick-started that revolution in the mid 15th century and even if we allow that it took a couple of centuries before the full impact of mass communication/media shook out, we should still be seeing these proto-national imagined communities emerging well before your 1800s mark. Anderson also highlights the way that nationalism appears as a nice means of legitimising the state and mobilising loyalty towards it as belief in monarchies and the divine right of kings, which previously fulfilled those roles, was challenged both intellectually (the Enlightenment) and practically - e.g. the French revolution (1789), or Glorious Revolution in England (1688) - which are again all obviously pre-1800.

(1/2)