Rajoy said "the most likely thing is that there will be elections on June 26th," according to a conversation overheard with British Prime Minister David Cameron at an EU summit in Brussels.
"We have an investiture ceremony in March and I believe it will not work out," Rajoy was heard telling Cameron, apparently unaware that he could be heard on camera.
Vuelve a ver el momento en el que Rajoy le dice a Cameron que "lo más probable" es que vuelva a haber elecciones https://t.co/oLkLpPQTZb— Antena3Noticias (@A3Noticias) February 18, 2016
He made the comments as Spain's Socialist chief Pedro Sanchez is struggling to form a minority government.
Sanchez, whose party came second in the December 20th general election, was nominated by King Felipe VI earlier this month to negotiate a coalition after Rajoy declined an offer from the monarch to lead the first round of coalition talks.
Rajoy's conservative Popular Party (PP) won the most seats but lost its absolute majority in parliament in the election which left the assembly fractured along four main formations - none with enough seats to govern alone.
The PP, which has been tained by a string of corruption scandals, could not find partners to give it a ruling majority and with Sanchez yet to make significant progress in his talks with other parties to gather support, the prospect of fresh elections is mounting.
He has a little over two weeks to try and form a coalition government that will be put to the test in a parliamentary vote of confidence scheduled to he held on March 2nd or the next day.
"I am working for Spain to have a progressive government while others in Brussels already talk of new elections. Pitiful," Sanchez wrote in a Twitter message after Rajoy's spoke.
With the Popular Party and the Socialists refusing to support each other, Sanchez will need to win over at least one of two new parties which won support in parliament for the first time in the December polls - market-friendly Ciudadanos and anti-austerity party Podemos.
Podemos had refused to negotiate with the Socialists if they also chat to Ciudadanos, which it considers to the right, an ultimatum rejected by Sanchez.
But in a possible breakthrough to the deadlock Podemos chief Pablo Iglesias said he had agreed to four-way talks between the negotiating teams of his party, the Socialists, smaller far-left party Izquierda Unida and Compromis, a regional grouping from Valencia in eastern Spain.
"It's a good idea... We're fully available for our teams to meet and talk," he said.
A coalition between the four parties is still far from an agreement, with the Socialist and Podemos divided over key policy area.
Podemos for example strongly backs a referendum on independence in the wealthy northeastern region of Catalonia which Sanchez opposes.
Sanchez needs an absolute majority to be voted through, and if he does not succeed, another poll takes place 48 hours later, where Sanchez will only require a simple majority.
If both fail, a two-month countdown begins from the first vote, at the end of which new elections will be called if no solution is found.
Recent polls suggest that Spain's four main parties would obtain roughly the same result as they did in the December 20th election -- though some indicate Podemos could overtake the Socialists as the second-biggest party, surpassing the Socialists.