Special forces is somewhat vague and can encompass many different military actions throughout history. In a way we can consider Alexander's companion cavalry special forces, or even the Roman Trarii and they may have been perceived that way at the time. However, I think your post is more specifically referring to individual military units designed and purposefully trained in covert actions, or our modern comprehension of what special forces do. Now this post will discuss the modern beginnings of naval special forces. There very well may be earlier examples of paratrooper operations, or espionage that can be considered actions of special forces, however I am not qualified to comment on that.

The definitive beginnings of naval special forces and our modern comprehension of where the US Navy SEALS gain their inspiration is from, surprisingly, the Italian Regia Marina in WW2.

I'll start with the idea which stems from WW1. Italy had a relatively inadequate Navy especially compared to the Austro-Hungarian Empire, who massed her Navy at Pola Harbor a stones throw across the Adriatic Sea. The Italian Regia Marina (Royal Navy) knew she couldnt face the Habsburg fleet in a Mahanian type naval battle so a few officers began to toy around with unconventional warfare. The first and only attempt of a "special operations" raid on Pola Harbor occurred on November 1, 1918, when Raffaele Paolucci and Raffaele Rossetti piloted a "manned torpedo" called the Mignatta and sank the battleship Jugoslavij. Keep in mind this was in the final days of WW1.

Skip ahead to WW2, Italy realizes she will be facing off against France and Great Britain in the Mediterranean. The Italian surface fleet was very modern and equally impressive in size. Though still outmatched in quantity of ships, many believed Italy's modern cruisers and Battleships would outmatched Britain's aging fleet. However, following crushing defeats at Taranto and Cape Matapan in early 1941, Italy again began to test unconventional covert actions using this "manned torpedo" technique. The Mignatta of WW1 was the inspiration for the Maiale of WW2. This was a 2 seated torpedo to be piloted by Frogmen who would attach it to the bottom of enemy ships hulls with a timed fuse. However, the Italians had effectively mastered deep sea diving and used this practice in their operations. The Italian Frogmen of the Decima MAS special forces can be credited with the first successful application of naval diver warfare. In fact, the watches and gauges each member used were hand made by Panerai, a popular watch company. In fact they still like to market their connection to the Xa MAS. If you ever walk past a Panerai store and see this in the window, that's the Maiale.

Anyways, under the command of Junio Valerio Borghese, these Frogmen would depart from the submerged submarine Scire. They were shockingly successful on their simultaneous raids at Gibralter and Alexandria. I will copy/paste the statistics from Wikipedia:

In more than three years of war, the unit destroyed some 72,190 tons of Allied warships and 130,572 tons of Allied merchant ships. Personnel from the unit sank the World War I-era Royal Navy battleships HMS Valiant and HMS Queen Elizabeth (both of which, after months of work, were refloated and returned to action), wrecked the heavy cruiser HMS York and the destroyer HMS Eridge, damaged the destroyer HMS Jervis and sank or damaged 20 merchant ships including supply ships and tankers. During the course of the war, the Decima MAS was awarded the Golden Medal of Military Valour and individual members were awarded a total of 29 Golden Medals of Military Valour, 104 Silver Medals of Military Valour and 33 Bronze Medals of Military Valour.

The Xa MAS were the direct inspiration for the US Navy SEALS because of how successful and underappreciated their actions were.

So as far as our modern interpretation of naval special forces is concerned I would say the first successful application was used by the Italian Frogmen of the Decima Flotiglia MAS in WW2

Sources:

Frogmen: The First Battles by William Schofield, P. J. Carisella

Sea Devils written by Junio Valerio Borghese himself

[Comando Supremo "Decima MAS Strike on Alexandria"] (http://www.comandosupremo.com/strike-on-alexandria.html)

And my own short biography I wrote on Borghese

Firstly: Sapkowski, the author of the Witcher books, is known for his use of anachronisms for comic effect and to discuss modern-day issues in his fantasy books. See this Publisher's Weekly review of one of the translations of a book of his, for example, which refers to mages discussing preserving endangered species of magical animals: http://www.publishersweekly.com/978-0-316-21913-6

The Temerian Special Forces should be seen in this light. They are not -meant- to be historically accurate, and neither are their tactics.

Game of Thrones, on the other hand, is more an example of events moving at the speed of plot. But raids by picked bodies of men certainly happened.

Elite units akin to modern-day special forces are another matter, though. Other posts in this thread have mentioned the Theban Sacred Band, but that was more of an elite unit which got a place of honour in the ordinary battle-line. The Roman Praetorians were mentioned, but those are an imperial bodyguard unit. Bodyguards occur in many places and cultures, but they were not used like special forces as far as I can tell.

The closest thing to troops being used as "special forces" that I can think of, would be in the army of Alexander the Great. Arrian often mentions that when confronted with some special obstacle or defence, Alexander would peel off certain elements of his army such as his Agrianian light infantry and Hypaspist elite heavy infantry and the Companion cavalry.

For example, when Alexander discovers the Cilician gates are held against him:

"he left Parmenio there with the regiments of infantry which were more heavily armed; and about the first watch, taking the shield-bearing guards, the archers, and the Agrianians, he advanced by night to the Gates, in order to fall upon the guards when they least expected it. However, his advance was not unobserved ; but his boldness served him equally well, for the guards, perceiving that Alexander was advancing in person, deserted their post and set off in flight."

Or later, when he finds that the Persians have built a wall across the Persian gates, and prisoners tell him there is a very difficult and narrow mountain pass he might take to get around it:

"Alexander advanced by night, and travelling about 100 stades, he took the shield-bearing guards, the brigade of Perdiccas, the lightest armed of the archers, the Agrianians, the royal squadron of cavalry Companions, and one regiment of cavalry besides these, containing four companies; and wheeling round with these troops, he marched towards the pass in the direction the prisoners led him."

This works out great:

"Falling upon the first guard of the barbarians before daylight, he destroyed them, and so he did most of the second ; but the majority of the third guard escaped, not indeed by fleeing into the camp of Ariobarzanes, but into the mountains as they were, being seized with a sudden' panic. Consequently he fell upon the enemy's camp at the approach of dawn without being observed. At the very time he began to assault the trench, the trumpets gave the signal to Craterus, who at once attacked the advanced fortification." [Craterus had been left in command of Alexander's main force] The enemy, surrounded, falls into a panic and are utterly defeated.

Or when storming a city: (Oyeopolis)

"he took the body-guards, the shield-bearing guards, the archers, and Agrianians, and made his way secretly into the city along the channel, at first with a few men, while the barbarians had turned their attention towards the military engines and those who were assailing them in that quarter. Having from within broken open the gates which were opposite this position, he gave an easy admittance to the rest of his soldiers."

All quotes are from Arrian's "The Anabasis of Alexander."

Again, these are not dedicated special forces in the modern sense, but they -are- elite troops picked for special assignments, selected according to their abilities. The Agrianians in particular were a mountain-people, very skilled at fighting with the javelin, and very much suited to such operations when backed up by heavier troops.

(If anybody has other ancient or medieval examples, I'd be thrilled to hear them.)

(edited to improve the link, formatting)

The closest thing I can think of to modern day "special forces" during that era is the Sacred Band in Thebes, c. 370 BC. The Sacred Band has been described as one of Thebes' military advancements around this time, alongside the stacked phalanx and more extensive use of cavalry units.

The Sacred Band was an elite corp of 300 soldiers, 150 pairs of male lovers. The source I read claims that they were superior because they would want to impress their lover and not appear cowardly; I question how accurate that is, but that's just what the source says.

They saw their first use in the Battle of Leuctra (371 BC), during which Thebes battled Athens and Sparta. Thebes used a new battle strategy during this battle. They positioned their hoplites to the far right, a fifty row deep stack of soldiers to the left. They had cavalry units and the Sacred Band even farther left. The idea was to use the impressively stacked left flank ("battering ram" troops + Sacred Band) - who would lead the charge - to smash through Sparta's right flank; this worked well and they overwhelmed Spartan forces. At this point the Sacred Band combated Sparta's sides. This was an overwhelming defeat for Sparta; they surrendered and retreated.

Now as far as small units go, the Sacred Band was relatively small. It sure wasn't "20 men" but while the battering ram consisted of 50 rows of ordinary soldiers - an astounding number - the Sacred Band was only 300. There was at least some idea that these 300 troops were more specialized than the rest.

Source: "The Greeks: History, Culture, and Society" by Ian Morris

Would ninjas (I know their actual existence is disputed) or Arabic assassins(hassashin?) not travel in units or otherwise meet the requirements drawn out in the OP? Sorry if this is an irrelevant comment.

Raiding seems to be one of the oldest forms of warfare, and may rthe main form of warfare for societies without logistics, so I'm not sure it really had a beginning. Here is a reference to raiding parties in Spain in 1100. Or check out the Yanomami.

I'm not sure 20 men ever stopped an army by burning their supplies. Seems doubtful that an army would put it's food supply into a highly flammable unguarded central store. No one would deploy armies if they could be destroyed by 20 men using a simple tactic. The realistic version of Ramsay's move would be destroying all the food, wells, and warm housing for miles around. That could destroy an army in winter.

Would the Dutch marines count as a special force. Or (only example I know from the Roman Empire) the Dutch Bataven were used by the Romans as amphibious attack troops since they were able to cross rivers with equipment easily or so I read.

Could anyone elaborate?