On 27 July 2005, new Celtic manager Gordon Strachan's tenure started on a low note with a record loss to Artmedia Bratislava in Champions League qualification.
Strachan arrived from Southampton earlier that month, replacing Martin O'Neill. Celtic had finished as runners-up in the league in O'Neill's final season, which put them in Champions League's second qualifying round for 2005-06. There, they met Slovakian league winners Artmedia for what was the first competitive match of Strachan's time at Parkhead.
Playing at the Tehelné Pole Stadium in Bratislava, the former European Cup champions suffered an early setback when they lost striker Chris Sutton to injury. But his absence provided no excuse for the Celtic defense, who surrendered an easy tap-in goal to Juraj Halenár in the 43rd minute, giving Artmedia a 1-0 lead at the break.
Midfielder Blažej Vaščák doubled the hosts' lead in the 57th minute with a nearly identical goal, then Halenár struck again in the 76th minute with a blast from almost 25 yards out. Two minutes later, Martin Mikulič extended the lead to 4-0 by beating Celtic keeper Artur Boruc with a low ball at the near post. Halenár then did the same in the 89th minute to seal the 5-0 victory--Celtic's worst loss in European competition.
The Glasgow side won the second leg 4-0, but lost 5-4 on aggregate to exit the competition. Artmedia, led by manager Vladimir Weiss, eventually reached the group stage where they finished third behind Inter and Rangers.
Strachan remained with Celtic for four seasons, winning three league titles, one Scottish Cup, and two Scottish League Cups.