SAS first service April 26 1959 on the Copenhagen - Munich - Vienna - Athens - Istanbul - Beirut service.
http://www.scanliners.com/lcc.htm
Air France first service May 12 1959 on Paris Orly - Rome - Athens - Istanbul
http://www.airliners.net/aircraft-da...ts.main?id=372
Dates are also from the definitive Caravelle book I have here, alas print only (and in French). You'll notice the aircraft started off on lengthy multi-stop services to the Middle East rather than on the shorter European trunk routes it later became associated with.