I'm using the wikipedia as my main source here, but it's conveniently backed up with a painting providing evidence.
The first use of observation balloons I know of was in the Battle of Fleurus in 1794. The balloon can be seen in this illustration and on this painting (I'm saw that last one in Versailles and wondered about the balloon at the time, so I looked it up. I'm no expert on this at all).
Reports on its usefulness vary, but the balloon survived and during the battle was able to send information to the commanders via dropped messages and a semaphore.
You can still see one of these balloons on display in the Museum of Military History (Heeresgeschichtliches Museum) in Vienna. This one was captured at the Battle of Würzburg.
I am thinking the US Civil War may have had them because they show up in Jules Verne's book The Mysterious Island but I have no proof.