A local art expert quoted by the Polish newspaper Gazeta Wyborcza said while it was impossible to place an exact price on collection, he was sure it was worth "millions of euros".
The collection, having suffered from its 66 years in the outhouse, has now been moved to a museum in Szczecin.
"Many of the pictures are in a terrible condition and we're trying to identify them and find out where they came from," said Przmyslaw Kimon, spokesman for Szczecin police. "Some of them are Italian so we're in contact with the Italian authorities, and we are also working with Interpol."
Most theories revolve around the possibility that the bricklayer had somehow managed to get hold of a collection of looted art, abandoned in the chaotic last weeks of the Second World War as Germans put life before property in their efforts to escape the advancing Red Army.
During the war German forces indulged in looting on a massive scale in the occupied territories, stripping museums and private collections bare. While many pieces were recovered after the war others disappeared without trace, especially in eastern Europe, which suffered from widespread destruction and huge movements of refugees.
One theory goes that the bricklayer's house had once belonged to art dealer, and the dealer's art had stayed in the house after its owner disappeared.
Another possibility is that Antoni M. had discovered crates of looted art the Germans had failed to transport west before the end of the war.
Possessing an interest in art he decided to keep the paintings rather than turn them into the authorities.
He also decided to keep them out of public sight. Stashing them in hiding places in his outhouse, he made the building off-limits to even his closest family.
The news of the discovery was welcomed by Leszek Jodlinski, director of the Silesia Museum in Katowice, one of the museums stripped bare by the Nazis during the war, and the former home of the Czajkowski lithograph.
"For us the picture is beyond value priceless," he said. "When you lose everything it is so important to get something back." Mr Jodlinksi added that he was confident there were other works of art stolen from his museum amongst the bricklayer's paintings as it was unusual for collections to be broken up.