According to Britannica's online article on Hagia Sophia:
The original church on the site of the Hagia Sophia is said to have been built by Constantine I in 325 on the foundations of a pagan temple.
The article does not list a source for this information and I can't seem to find any further information about it. Is there any evidence Hagia Sophia was built on the foundations of a pagan temple?
Going beyond E.B. or Wikipedia:
The official website of the Hagia Sophia Museum (at its former domain, link now dead) stated
The first church [at the H.S. site] was constructed by Emperor Konstantios [i.e. Constantine's son] (337-361) in 360. The first church was covered with a wooden roof and expanded vertically (basilica) yet was burned down after the public riot that took place in 404 as a result of the disagreements between Emperor Arkadios’ (395-408) wife empress Eudoksia and Istanbul’s patriarch Ioannes Chrysostomos, who was exiled. [...] No remains have been recovered from the first church; however, the bricks found in the museum storage branded ‘Megale Ekklesia’ are predicted to belong to the first construction.
The current official website of Hagia Sophia Museum and Foundation now states
Hagia Sophia is a work that was constructed three times in the same location. Today’s Hagia Sophia is known as the “Third Hagia Sophia”. The first construction of Hagia Sophia started during the reign of Constantine I, who accepted Christianity as the official religion of the Roman Empire. This building, which was constructed as a basilica with a wooden roof on the first of the seven hills of Istanbul and was called "The Great Church" at the time, was opened during the reign of Constantine II in 360. There is no remnant from this structure, which was largely devastated as a result of a fire that broke out in the revolt that started in 404.
The website Hagia Sophia says
Known as the “Great Church” or “Magna Ecclesia” in Latin, the first church was built at the same location where there had been a pagan temple before [emphasis mine]. It was Constantius II who inaugurated Hagia Sophia on 15 February 360. From the chronicles of Socrates of Constantinople, we know that the church was built by the orders of Constantine the Great.
Prokopius' book Buildings of Justinian, a translation of which was kindly linked to by @user2448131 gives a detailed description of the Hagia Sophia, its construction, and its beginnings post Nika revolt, but does not make any mention of pagan "foundations".
As for other historical source, there seems to be a distinct dearth when searching on that topic: there are many sites or excerpts with circular quoting referring to the pagan temple. This one stating
Some say that the site was first a pagan temple in honor of Apollo and Venus.
Which is one of the few that actually identifies the deities. As a number of other sources state Greek temple, we'll have to presume that would have been Aphrodite?
Here is a most intriguing abstract about the construction of the Hagia Sophia. It was actually designed by a pagan! Sadly the site requires registration and acedemic credentials.
A figure overlooked in scholarship on Hagia Sophia is Phokas, the praetorian prefect of 532 under whom construction of the church began. He was a pagan who eventually took his own life in one of Justinian’s purges. His initial supervision of the construction of Hagia Sophia is attested by Ioannes Lydos, himself a pagan intellectual, who praised Phokas in superlative terms, despite Phokas’ infamous death. Consideration of all the evidence for an architect of Hagia Sophia, Anthemios of Tralleis, beyond the literary sources usually cited, strongly suggests that he belonged to the pagan wing of the school of Ammonios of Alexandria, as did the architect Isidoros of Miletos. Material presented here explains how the last pagans of New Rome contributed to the making of Hagia Sophia and suggests how they may have interpreted the monument on their own terms.
On the spur of the moment, I contacted, going first via Prof. Mary Beard, her husband Prof. Robin Cormack, specialist in Byzantinistic or, as Wikipedia states, he is a British classicist and art historian, specialising in Byzantine art. He was Professor in the History of Art, Courtauld Institute of Art, University of London, 1991–2004. Despite traveling in Turkey as I write this, he was kind enough to respond he writes:
Just a short answer as we are in Turkey just now. Archaeologically there is no clear indication, as the Constantinian church underneath the present church has not been excavated. In the course of time all sorts of mythic stories about the city and its origins developed. There is a really good book about this - Gilbert Dagron, Constantinople imaginaire . He collects all the stories and assesses them
The title of the book sounds French, so I'd either have to brush up a lot on my rudimentary knowledge or some other kind soul, fluent in French, can provide information from that book.
LATE EDIT:
It's been two years and revisiting this, I had totally missed that the OP @Notaras had provided a very interesting link in chat (which I so rarely check) to an academic paper titled Pre-Constantinian Floor Mosaics in Istanbul (registration required).
This paper itself quotes research and speaks about a mosaic found, not at Hagia Sophia but at Hagia Eirene. It's dated, depending on researcher as late as the fifth and as early as the second century CE. The paper goes on to say
Medieval sources do not inform us about the location of the temples in the city, except that the temples of Apollo, Artemis, and Aphrodite were on the acropolis.6 We also know that Septimius Severus built a temple dedicated to Apollo-Helios on the acropolis, which was extant at least until the reign of Leo I.7 In the debris to the north of Hagia Eirene, at the western edge of the acropolis of ancient Byzantion, Ramazanoglu found an inscription reading, perhaps in reference to the same temple that Septimus Severus had built, “Gaios … Skumnos made one of the … propylons of the temple of Apollo.”8 Thus, Ramazanoglu identified a structure that he ex cavated right outside the southern wall of the church, with the temple of Apollo and the mosaic floor with the Temple Aphrodite next to it (fig. 3).9 However, his attribution and dating are problematic, since they contradict both the historical sources and our current knowledge of the chronological development of ancient mosaic making.
This would mean that the temple(s) of Apollo and Aphrodite referred to earlier were not at the site of H.Sophia but rather at H.Eirene. However a quick glance at a map of modern Istanbul shows those two to be virtually next to each other.
