Ονομάστηκε έτσι λόγω της θέσης της, κάτω από τη Βασιλική Στοά που βρισκόταν δυτικά του Αυγουσταίου. Η Στοά χτίστηκε πιθανώς από τον Μεγάλο Κωνσταντίνο αλλά καταστράφηκε περίπου το 475. Η κινστέρνα διαμορφώθηκε ως έχει σήμερα, όταν ξαναχτίστηκε γύρω στο 542 μ. Χ. από τον αυτοκράτορα Ιουστινιανό Α', μετά την περίοδο της στάσης του Νίκα, για την ύδρευση της Κωνσταντινούπολης σε ολόκληρη τη βυζαντινή περίοδο και για να προμηθεύει νερό στο παρακείμενο Μέγα Παλάτιον, όπου είχε την έδρα του ο βυζαντινός αυτοκράτορας.

Ήταν ένα από τα σημαντικότερα δημόσια έργα του Ιουστινιανού και εξαίρετο δείγμα βυζαντινής μηχανικής. Ο Έλληνας ιστορικός Προκόπιος της Καισαρείας παραδίδει μια λεπτομερή περιγραφή της κινστέρνας στο έργο του "Περί των κτισμάτων", σημειώνοντας πως φρέσκο νερό μεταφερόταν σε αυτή με τη βοήθεια αγωγού, ενώ εκεί αποθηκευόταν επίσης μια ποσότητα νερού, το οποίο συνήθως αφθονούσε σε άλλες εποχές εκτός του καλοκαιριού.

Η συμμετρία, το μεγαλείο του σχεδιασμού και η πολύπλοκη υδρομηχανική της Βασιλικής Κινστέρνας είναι μοναδικά. Οι 336 εντυπωσιακοί κίονες είναι διατεταγμένοι σε 28 σειρές ανά 12,σε απόσταση 4 μέτρων μεταξύ τους (από κεντρικό σε κεντρικό σημείο) και φανερώνουν την κατάκτηση της αρχιτεκτονικής που βασίζεται στον πολλαπλασιασμό μιας βασικής μονάδας. Η θολοδομία είναι επίσης υποδειγματική. Τα σταυροθόλια έχουν κατασκευαστεί όχι από ρωμαϊκό ασβεστοκονίαμα αλλά από μονές σειρές οπτοπλίνθων, στοιχισμένων εγκάρσια στον άξονα του θόλου και μπηγμένων μέσα σε πολύ παχύ κονίαμα . Αυτό το είδος της εκπληκτικά ελαφριάς θολοδομίας αργότερα εξελίχθηκε και χρησιμοποιήθηκε και σε άλλα δημόσια κτήρια και εκκλησίες, όπως στους τρούλους και τα ημιθόλια της Αγίας Σοφίας και τους πτυχωτούς τρούλους του ναού των Αγίων Σεργίου και Βάκχου. Είναι επομένως φανερό ότι η χρήση του τετράγωνου χώρου ως βασικής μονάδας και η θολοδομία με οπτοπλίνθους στη Βασιλική Κινστέρνα έπαιξαν σημαντικό ρόλο στην παγίωση ενός κανόνα για τα αυτοκρατορικά καθιδρύματα της Ύστερης Αρχαιότητας και του πρώιμου Βυζαντίου στην Κωνσταντινούπολη.