The leader of the “Yes” movement, Jeffrey Pullicino Orlando, of the governing Nationalist Party, said the result was significant.
“It brings Malta into a new era where the state and the Church are separate,” Mr Orlando is quoted as saying by Efe news agency.
Malta is one of only two countries in the world (with the Philippines) to ban divorce – apart from the Vatican.
Chile was the last country to legalise divorce in 2004 after overwhelming public pressure.
Maltese voters were asked whether parliament should introduce a new law that would allow couples to obtain a divorce after four years of separation.
Previously, couples could apply for a legal separation through the courts, or seek a Church annulment – a complex process that can take up to nine years.