The Croatian ninth seed won the prestigious grass court tournament at Queen's Club in 2012, but his hopes of doing the same this time around came to an early end as Australian Matosevic surged to a 6-4 6-4 win.
Matosevic produced a clinical performance as he needed just two breaks of serve to set up a second-round clash with Lukas Lacko, who prevailed over Matthew Ebden 7-6 (12-10) 5-7 6-4.
But, while Cilic crashed out, there were no such difficulties for Tomas Berdych, who is through to the third round thanks to a 7-6 (7-3) 5-7 6-4 success over dogged Australian James Duckworth.
Joining Berdych in the last 16 is fourth seed Grigor Dimitrov of Bulgaria after he won 82 per cent of points on his first serve in seeing off a spirited effort from Britain's James Ward, winning 7-5 6-3.
Kevin Anderson ensured there would be no home success on Tuesday, the South African comfortably dispatching Brit Daniel Evans 6-2 6-3 in his second-round match.
Spain's Feliciano Lopez beat Serbian Dusan Lajovic 6-3 6-7 (3-7) 6-1 in a match held over from Monday, and Canadian 11th seed Vasek Pospisil was made to work hard to overcome Paolo Lorenzi 6-3 3-6 6-3.
Radek Stepanek was a straightforward winner as the Czech hammered Kazakhstan's Mikhail Kukushkin 6-4 6-1, yet there was no such fortune for Julien Benneteau, the Frenchman losing in three sets to Victor Estrella of the Domincan Republic.
Estrella appeared on course for defeat after losing the first set on a tie-break, but displayed admirable spirit to recover and knock out a player ranked 49 places above him 6-7 (3-7) 6-3 7-6 (7-3) in two hours and 16 minutes.
There was more French disappointment as Benoit Paire lost to Jarkko Nieminen 2-6 6-3 7-6 (7-1), although Edouard Roger-Vasselin did see off Evgeny Donskoy of Russia 6-3 6-7 (11-9) 6-1.
Dmitry Tursunov powered past Igor Sijsling 6-3 6-4 in just 53 minutes, while Sam Querrey beat Denis Kudla 6-4 6-3 in an all-American clash to reach the third round.
Elsewhere in the draw, there were wins for Marcos Baghdatis, Denis Istomin and David Goffin.