Čeh started his career with his hometown club Drava Ptuj. By the age of 17 he was playing in the first team in the 2. SNL. In the 1996–97 season he moved from Drava to Maribor, later spending one season at NK Olimpija before returning to Maribor and then moving on to Club Brugge. His first season at the club brought success in the Belgian Cup, and the following season Čeh helped the club win their 12th league title. In August 2002 he scored a late equalising goal in the second-leg of Brugge's Champions Leaguethird round qualifying tie against Shakhtar Donetsk. Brugge then went on to qualify through a penalty shootout. In 2005 Čeh was sold to Austria Wien. Jupiler League team Charleroi tried to buy Čeh in late August 2006 but in 2007 Čeh left Austria and signed for Russian Premier Liga side FC Khimki, where the Slovene playmaker was given the number 10 shirt. On 5 January 2009 he left Khimki and moved to Greek club Panserraikos. After a short spell in Greece, he signed for Rijeka, spending a season there before moving on yet again to play in Israel.
In late April, 2011, it was revealed by the Slovenian media that Maribor police department is, for the past six months, investigating an illegal betting organization and six individuals, four of which were from the Maribor area and had already been taken into custody. The Police has also revealed that two other collaborators are still at large and that one of those is Goran Šukalo, who allegedly invested over 1,9 million euros in the organization, in 2011, the majority of which he collected from other professional players. Šukalo categorically denied his involvement in the matter, however, it was revealed by the media and the police that investigators had been tapping the phones of the four persons currently in custody and have recorded a conversation between Šukalo and the leader of the illegal organization Kosta Turner, when Šukalo revealed that another football player, Nastja Čeh, is still owing him 73 thousand euros and is avoiding payment. Allegedly this is the reason why Čeh pawned his property near Ptuj to Kosta Turner, what is visible from the official real estate papers. In January 2012, the general prosecutor on the District Court in Maribor proposed an indictment of six individuals, ring leaders of the illegal betting organization, in light of new evidence against them. The organization allegedly accepted a total of 43 million euros of bets, with 2,53 million euros being placed by Čeh.