If there are Predicates before Predicate Calculus, why is it called such? In my understanding, predicates are synonyms of relations: mappings of an ordered set (a,b) to the set of values "True" and "False"
Well, propositional calculus comes before predicate calculus, and we have relations in propositional calculus.
I mean, I believe that all connectives are relation symbols: sentences involving connectives must be mapped either to "True" or to "False", in other words, they have truth values.
This leads to me to the question: why is Predicate Calculus called Predicate Calculus if there are predicates in Propositional Logic?
 A: The name predicate calculus has an historical heritage ...
Today we prefer to call it first-order logic.
For the "founding fathers" : Frege, Russell, the distinction between propositional and predicate calculi were not relevant; see Principia Mathematica and The Notation in Principia Mathematica.
In the first modern mathematical logic textbook :


*

*David Hilbert & Wilhelm Ackermann, Principles of Mathematical Logic (2nd ed - 1937; 1st German ed 1928)


we can find the distinction between sentential calculus and predicate calculus; see page 44 :

So far, the form of our logical calculus is adequate for the precise rendering of those logical connections in which the sentences appear as unanalyzed wholes. For the purposes of logic in general, however, there is no question but that the sentential calculus is inadequate. We cannot even obtain from it conclusions 
  of the simple kind which are referred to in traditional logic by the catch-words "Barbara," "Celarent," "Darii," etc. For example, it would be in vain to search for the formal rendering of the logical relation expressed in the following three sentences: 

"All men are mortal; 
Socrates is a man;
therefore, Socrates is mortal." 

The reason for this is that inferences of this sort depend not only upon the sentences as wholes, but also upon the inner logical structure of the sentences which is expressed gramatically by the relation between subject and predicate [emphasis mine : the reference is to "traditional" logical terminology] and which plays an essential role. 

In the early authoritative textbook :


*

*Alonzo Church, Introduction to Mathematical Logic (1956)


we have : propositional calculus and functional calculus of first order.
According to Church's Historical note [page 288] :

the first explicit formulation of the functional calculus of first order as an independent logistic system is perhaps in the first edition of Hilbert and 
  Ackermann's Grundzüge der theoretischen Logik (1928).
For the functional calculus of first order and thc functional calculus of 
  second order Hilbert and Ackermann in their first edition employ the names "engerer Funktionenkalkül" and "erweiterter Funktionenkalkül" respectively. In their second edition (1938), partly following Hilbert and Bernays (1934-1939), they change these names to "engerer Pdidikatenkalkül" and "Pradikatenkalkül der zweiten Stufe." This change is based on a usage of the word "Pradikat" (predicate) which appears already in the first edition of Hilbert and Ackermann, but which we wish to avoid.

