The smallest officially-recognised state is the Vatican City; the city-state of the pope, and comprises of little more than St Peter's, the Papal Palace and the surrounding out-buildings and gardens; the pope also has a pastoral residence somewhere in the country outside of Rome.
But the smallest de facto recognised state (meaning its territorial rights are recognised by its neighbours and it possesses observer status in the UN), is the Sovereign Military Order of Malta. Their independent "territory" comprises of two small palaces in Rome, and a castle (in need of restoration) in Valletta harbour, Malta. The citizens of this "state" are modern-day knights; the descendants of Crusaders - all three of them. These three people have their own "SMOM" passports recognised by a number of states in the world (including Italy and Malta), although the UK isn't one of them. The unofficial population of SMOM is in the tens of thousands, though these "unofficial" citizens cannot use SMOM passports, and use those of their country of origin.
The story of these contemporary knights begin back in the Crusades. Their ancestors were the Knights Hospitaller, who ran a hospital in Jerusalem prior to the First Crusade in 1089. After that, their fortunes prospered in the Holy Land. When the Saracens overran Jerusalem a hundred years later, they fled north to the port of Tripoli (in modern-day Lebanon), and when that was overrun in in 1291, they were offered sanctuary in Cyprus. The knights (now called the Knights of St John) then decided to conquer a territory of their own, and settled on the island of Rhodes and its nearby territories.
The knights made Rhodes their own territory, holding it from 1309 until they were finally forced to flee after a six-month siege by Ottoman Sultan Suleiman the Magnificent in 1522. After hanging out in Sicily for a while, the Holy Roman Emperor gifted the knights the territory of Malta, as well as the North African port of Tripoli (Libya's capital city today) in 1530. The knights made this their own independent state, like Rhodes before it, building a castle in the harbour in Valletta to use as their stronghold. And they held on to Malta until Napoleon decided Malta was of too much strategic importance, and that a late-18th-century Crusading state was an anachronism, and successfully invaded it in 1798.
Kicked out of their home of nearly three hundred years, the British Empire then forced the French from Malta only two years later, in 1800, and held on to it until Malta's independence after the Second World War. But the Knights of St John were again effectively homeless, some of them finding favour with the then Russian Tsar Paul I, others finding residence in the ports of southern Italy. Eventually, they found a permanent base in Rome in 1834 (at the time ruled by the Papacy, until its dissolution in the 1860s), where the knights was given two palaces for their own personal use, outside of foreign jurisdiction. These two palaces, the Magistral Palace and the Magistral Villa, are still the sovereign territory of the knights today, as well as the Fort of St Angelo in Malta.
Apart from this legal oddity that has allowed a modern-day Crusader-state to exist in the middle of Rome, there is another, even smaller "state" that exists as a de facto independent entity. It is called the Principality Of Sealand.
During the Second World War, the British military built a number of military platforms in the Thames estuary and a short distance off the coast of South-east England. One of them, called HM Fort Roughs, lies six miles off the coast, roughly east of Harwich. As with all the military installations, it was abandoned after the war, and in 1967 an enterprising couple, Major Paddy Roy Bates and his wife, decided to live there. The following year, when workmen were close to the occupied platform, Bates fired shots to ward them away. The issue went to court, and the judge ruled that as, at the time, the platform was beyond the UK's three-mile territorial waters, no charge could be sustained. So from a legal point of view, the self-styled "Principality of Sealand" was de jure a legally-separate entity.
The platform which Bates and his family live on comprises of two concrete hollow "supports" (which each have seven floors of living space, each floor consisting of one or two small rooms), and a platform above with a residential structure, a heli-pad, and a winch for supplies. It is, in effect, a large house at sea with office space.
Since the onset of the internet, the "government" of Sealand (the Bates family) has done what it can to make money out of their unique territorial status. It has tried to be an internet haven; that project fell through. It tried to sell the territory to Spain; that was not legally possible. Now the plan this year is to set up an Internet Casino.
There are many people involved in different ways with the "Principality"; check out their website if you want to find out the latest madcap adventures of Sealand.