What was first, sola scriptura or sola fide? I just watched a video with an Orthodox professor, in which he said that "Sola Scriptura" came first, and then "Sola Fide". Is that true? The best I can gather from the Wiki articles on these two topics is that both of them came pretty much simultaneously.

The video itself is in Russian.  Here is my translation of his words (starting at 5:57):


  …And all these new ideologues outraged by this so called scholasticism
  |of Roman Catholic Church| have declared, “The truth is only what the
  Scriptures say. Only the Scriptures and nothing else! Period. Let’s
  abandon all these theologians!” This apparently magnificent thesis
  made a big impression on many Christians. Because many had already
  been racking their brain over some speculations by some |theologians|
  like Duns Scotus or Thomas Aquinas. Indeed, their speculations were
  just abracadabra and no one really knew what to make of it.
  
  So, they said, “Only the Scriptures!” Perfect! Who would’ve dared say
  anything against that? It really sounded just perfect. 
  
  But what was the outcome of that? |The outcome of that was:| “You
  think this way?”, “And you think another way?”, “And you have yet
  another opinion?!” So, as a result, the whole Protestantism began to
  fall to pieces. Soon it was like peas spilled and scattered all over
  the floor. Everyone had his own opinion.
  
  And where was the criterion for determining who was right and who was
  wrong? How was one to know which opinion was correct? Well, it was
  already too late |to look for such a criterion|. There were no
  authorities anymore. The Fathers were no longer held as the authority.
  Each person now considered his own way of thinking and his own
  understanding as true. The truth for each person was now his own thoughts
  and convictions. And each one would claim now, “That’s how the Holy
  Spirit showed me this!” (|Of course, it begs the question,| “How can
  it be the Holy Spirit if you are arguing with one another and just
  can’t find any common ground in your understanding?!”) They were
  really now all scattered like peas on the floor! You see? This is how
  sometimes a very attractive thesis, which one would think shouldn’t
  cause any disagreement, can |turn out to be false|.
  
  So what did they finally arrive at? They arrived at another thesis,
  which came right after “Sola Scriptura”, and that thesis is
  indisputable in Protestantism – the whole Protestantism is standing on
  this thesis like on a strongest foundation. This thesis is “We are
  being saved only by faith” By what kind of faith? By believing that
  Jesus Christ is the Lord, that He has suffered on our behalf, that He
  has redeemed us from sin, that we are saved through His sacrifice…


So he seems to be claiming here that "Sola Fide" was put forth as a reaction to the many divisions among Protestants caused by "Sola Scriptura". Thus, his chronology is as follows:

Sola Scriptura –> divisions –> Sola Fide

This contradicts to a story that I heard before about Martin Luther climbing some ladder on his knees in some temple and suddenly recalling, if I remember correctly, Rom 1:17 ("The righteous will live by faith"), which happened even prior to 95 theses. 

However, I may have gotten this story wrong and my knowledge on Reformation is quite limited, so I don't know.
This is a complex topic, for at least two reasons: 1) there was a wide diversity of thought in the pre-Reformation and Reformation periods, and 2) today's definitions of sola scriptura and sola fide vary and the particulars can be difficult to trace within the pre-Reformation and Reformation periods, and any attempts to do so are naturally susceptible to bias.

For example, on one hand, one could argue that Alexei Osipov is simply incorrect – that the extreme version of sola scriptura that he is describing did not appear until the Radical Reformation (~1520s) and that Luther's doctrine of sola fide (~1515) predates that by several years. But many (mostly non-Protestants) would counter that the professor's description of sola scriptura substantially matches that of Protestantism generally, not just the Anabaptists of the Radical Reformation.  And of course, we're ignoring that many Protestants argue that both these doctrines can be found in the writings of the early church.

With those caveats, I'd argue that while Osipov's treatment is imprecise, his general point can be defended in two ways:


Many Pre-Reformation thinkers, like John Wycliffe (1320–1384) and John Huss (1372–1415), placed higher emphasis on the authority of Scripture than was expressed at the Council of Trent by the Roman Catholic church.  These Pre-Reformation thinkers, however, did not clearly articulate "faith alone."
Logically, sola scriptura comes before sola fide, because the doctrine of sola fide as argued by Luther and other Reformers was defended on the basis of the Bible against the tradition and authority of the Church.


Pre-Reformation

At the Council of Trent, the Roman Catholic Church held that both scripture and tradition were authoritative:


  Both saving truth, and moral discipline [...] are contained in the written books, and the unwritten traditions which, received by the Apostles from the mouth of Christ himself, or from the Apostles themselves (Session 4)


In contrast to this, many pre-Reformation thinkers placed a higher priority on Scripture.  Two notable names along these lines are John Wycliffe and John Huss, who both died over a century before Luther released his 95 theses.  These men opposed what they saw as abuse and excess in the Catholic church, and attacked a variety of the church's doctrines, including the papacy, transubstantiation, and indulgences, and often did so on the basis of the Bible.  John Wycliffe "recognised as an authority, apart from reason, only the Holy Scriptures, not tradition." (Lechler, 267)

However, these men did not lay out a doctrine of justification like that of sola fide.  Thus, if the views of Wycliffe on Scripture suffice as an example of sola scriptura as understood today, then it preceded the sola fide of Luther.

Sola scriptura logically antecedent to sola fide

Alistar McGrath writes:


  Every strand of the Reformation movement regarded Scripture as the quarry from which its ideas and practices were hewn (Thought, 91)


That is, in the Reformation, everything ultimately comes back to the authority of the Bible, including justification by faith alone.  We see this, famously, in Luther's 1521 statement at the Diet of Worms:


  Unless I am convinced by the testimony of the Scriptures or by clear reason (for I do not trust either in the pope or in councils alone, since it is well known that they have often erred and contradicted themselves), I am bound by the Scriptures I have quoted and my conscience is captive to the Word of God. I cannot and will not recant anything, since it is neither safe nor right to go against conscience.


When challenged, Luther naturally fell back to the ultimate basis for his beliefs, which he argued was the Bible – he didn't argue for sola scriptura on the basis of sola fide, but instead held that the things he believed were true because he found them in the Word of God.  Though this doesn't prove that sola scriptura chronologically preceded sola fide in the mind of any particular reformer, we can still say that the logical connection indicates that sola fide needed sola scriptura in order to stand and survive.

The origins of sola scriptura and sola fide

One of the difficulties mentioned above associated with this question is defining sola scriptura.  Alistar McGrath identifies three views that can feasibly carry this name:


Scripture and tradition are "coinherent or coterminous," that is, that Scripture alone is materially sufficient, and tradition acts as a reliable guide that defines the limits of acceptable interpretation


McGrath associates this view with Wycliffe, Huss, and the theologians of the schola Augustiniana moderna, that is, scholastics associated with Gregory of Rimini.

Scripture alone serves as the basis for faith and practice


This is the view expressed by Ulrich Zwingli at Zurich, resulting in the mandate that only Scripture could be used as the basis of public preaching (Origins, 45; see Wikipedia).

Tradition has no relevance in the interpretation of the Bible; "every individual or community is free to interpret the Bible without reference to the Christian past."  (Thought, 100)


This is the view of the Radical Reformers (Anabaptists), originating in the 1520s.



The sola scriptura of the Reformers is often defined along the lines of #2 above.  But is #2 more like #1 or #3?  In his quote, Alexei Osipov closely associates #2 and #3.  But Alistar McGrath argues that #1 and #2 are more closely linked, arguing that the Reformation view was not an innovation in light of the diversity existing in late medieval catholicism (Origins, 145).  He also argues against a close connection between #2 and #3:


  It is totally wrong to suggest that the magisterial reformers elevated private judgment above the corporate judgment of the church or that they degenerated into some form of individualism. No leading mainstream reformer was prepared to abandon the concept of a traditional interpretation of Scripture in favor of the radical alternative. (Thought, 102)


The origin of the doctrine of sola fide, on the other hand, is usually seen to be more straight forward.  McGrath sees its roots in the schola Augustiniana moderna, but it first appears clearly in the thought of Martin Luther around 1515, in his "tower experience." (Thought, 120–21)  Thus Osipov's claim that sola fide appeared as the result of Protestant divisions is incorrect at least in the sense of its origin; it preexisted the division between the Reformers and the Radical Reformers.

Summary

Alexei Osipov lumps together the sola scriptura of the Reformers and that of the Radical Reformers in his discussion, which, depending on one's views on the Reformation, may or may not be agreeable.  But noticing this reveals the difficulty inherent in identifying the origin of sola scriptura and thus its connection with the Reformer's sola fide.  Still, it seems safe to agree with Osipov's general point, that the doctrine of sola scriptura precedes that of sola fide, both chronologically and logically, in the context of the Reformation. 



References


Lechler, Gotthard Victor, John Wycliffe and His English Precursors
McGrath, Alister, Intellectual Origins of the European Reformation
McGrath, Alister, Reformation Thought