Are there examples of statements that have been proven whose consistency proofs came before their proofs? I'm wondering if there are examples of statements that have been proven whose consistency proofs came before the proofs of the statements themselves.
More informally, I'm wondering how promising in general is the approach of attempting a consistency proof for a statement when faced with a statement that seems true but difficult to prove.
Background:
If a statement is provable from a set of axioms, then that statement is obviously consistent (assuming the set of axioms is consistent).  So provability is stronger than consistency.  This might lead one to think that constructing a consistency proof for a statement should be strictly easier than constructing a proof.
Yet consistency proofs (at least oft-cited ones, for example those by Godel and Cohen about the Continuum Hypothesis) seem to require a high level of sophistication (though this might be a byproduct of the fact that consistency proofs like these are for the special class of statements that cannot be proven).
For statements that can be proven then, are there cases where their consistency proofs are easier or came before the proofs themselves?
Update:
Thanks a lot, everyone, for the great answers so far.  The number and existence of these examples is interesting to me, as well as the fact that they all rely on the same technique of first proving something using an additional axiom (an approach first suggested by Michael Greinecker).  That hadn't occurred to me.  I wonder if there are other approaches.
 A: Baumgartner and Hajnal showed that if $\Phi$ is an order type with the partition property $\Phi\rightarrow (\omega)_\omega^1$  then $\Phi\rightarrow(\alpha)_k^2$ for all $α<\omega_1$ and $k$. This provided the solution to problems of Erdős and Hajnal [Axiomatic set theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967), pp. 17--48, Amer. Math. Soc., Providence, R.I., 1971; MR0280381 (43 #6101)]. 
 They proved this by first using Martin's Axiom and then appealing to absoluteness. Galvin later provided a purely combinatorial proof.
See 
Baumgartner, J.; Hajnal, A. "A proof (involving Martin's axiom) of a partition relation." Fund. Math. 78 (1973), no. 3, 193.
A similar example is provided by 
Farah,  Hrušák, and  Martínez Ranero in "
A countable dense homogeneous set of reals of size $\aleph_1$"
Fund. Math. 186 (2005), no. 1, 71–77. They construct a $\lambda$ set that is homogeneous in the sense that any two countable dense sets can be mapped to each other assuming CH and then obtain the result by appealing to Keisler's absoluteness for the logic of countable sentences.
A: Considering all the answers so far, I thought I might as well add one with a more topological flavor to it


*

*The existence of an L-space was known to be consistent for years (See The Handbook of Set-Theoretic Topology, Chapter 7, pg. 295). It was only recently that a ZFC construction was given here

*Some of the existence proofs for certain types of embeddings, and automorphisms between Boolean algebras have this flair to them, (See "The fourth head of $\beta\mathbb{N}$" by Ilijas Farah, in Open Problems in Topology II. pg 139.)

*Certain types of gnarly questions about coverings of $\mathbb{R}$ involving the forward and inverse images of $\aleph_1$ many continuous functions, have had some success with this see this answer
A: Let $c(X)$ denote the cellularity of the topological space $X$, that is the supremum of the cardinalities of its families of pairwise disjoint non-empty open subsets.
In the early 60's Kurepa asked:


Is there a compact Hausdorff space $X$ such that $c(X)<c(X^2)$?


and noted that if $\mathbb{L}$ is a Suslin Line then $c(\mathbb{L})=\aleph_0<c(\mathbb{L}^2)$.
So the consistency of a positive answer to Kurepa's question has been known since the first constructions of Suslin trees using forcing by Jech and Tennenbaum in the late 60s. Later Galvin was able to get a compact CCC space whose square is not CCC from the Continuum Hypothesis.
And while the existence of a CCC space whose square is not CCC is independent from ZFC (an arbitrary product of CCC spaces is CCC under $MA_{\omega_1}$ for example), in the mid 80s Todorcevic surprised everyone by constructing a compact space $X$ such that $c(X)<c(X^2)$ in ZFC.
http://archive.numdam.org/article/CM_1986__57_3_357_0.pdf
Todorcevic's paper contained many other ZFC constructions of objects whose consistency had been previously known, including higher cardinal generalizations of $S$-spaces and $L$-spaces.
A: Before the existence of a nontrivial surjection $f:\mathcal P(\omega)\to\mathcal P(\omega)$ satisfying $f(X)\supseteq X$ and $f(X\cup Y)=f(X)\cup f(Y)$ was proved in ZFC, it was proved under various additional hypotheses such as CH.
A: One of the main applications of Shelah's pcf theory is the celebrated theorem that if $\aleph_\omega$ is a strong limit, then $2^{\aleph_\omega}\lt\aleph_{\omega_4}$. 
The conclusion of the theorem, however, is an immediate consequence of the generalized continuum hypothesis, and so the consistency of this statement was known long before Shelah made his proof. The surprising aspect of the theorem is precisely the fact that it is provable without any assumption on the continuum function.
There are likely many other examples of statements that were first proved from a GCH assumption (or which are trivial under GCH), but for which later this assumption was removed. And indeed, in these cases the later more general arguments are also often more difficult, as you suggest. 
A: Here are my favorite examples of statements whose consistency was established and cherished before their proof.
1. The Keisler-Shelah isomorphism theorem stating that two elementarily equivalent structures have isomorphic ultrapowers (proved using in $ZFC+GCH$ by Keisler in 1964, and in $ZFC$ by Shelah in 1971).
2. Several algebraic results (normal forms, divison algorithms, etc) concerning the "left-distributive algebras of one generator" were first established by Richard Laver by assuming (very) large cardinals (known as (I3) in the literature). Later Patrick Dehornoy eliminated the large cardinal assumption in these results by giving a representation in the braid group. 
By the way, a left distributive algebra is a set with one binary operation * satisfying the left distributive law
$a*(b*c)=(a*b)*(a*c)$; the operation of conjugation in a group is an example. Here is an old paper of Laver about this topic; there is by now a large literature on the subject.
3. In some cases, the consistency proof of a statement $S$ can be combined with some absoluteness argument to yield a proof of $S$ (this was hinted at in the second example cited by Steprans). There are all sorts of absoluteness theorems in logic; the standard tool of the trade is the Shoenfield absoluteness theorem that shows that all sorts of consistency results can be translated into $ZFC$-proofs.
A: Todorcevic proved in ZFC that the two-element subsets of $\omega_1$ can be partitioned into $\aleph_1$ classes so that every uncountable subset of $\omega_1$ contains pairs from every class; in symbols, $\aleph_1\not\to[\aleph_1]_{\aleph_1}^2$. The straightforward proof of the same from CH was known to Erdős, Hajnal, and Rado many years earlier.
A: A very good example, I believe, is A. Blass' theorem that AC holds if and only if every vector space has a basis.
It was well established that the existence of a vector space without a basis is consistent with the negation of AC, by Lauchli, 1963. Only 21 years later it was proved that ZF+not AC proves such a vector space exists.
There are probably some other similar examples of equivalent assertions of AC of similar nature.
A: Inasmuch as the negation of a large cardinal axiom is automatically known to be consistent, theorems such as "there are no Moschovakis cardinals" were known to be consistent before they were proven outright. Unfortunately I don't recall the definition of a Moschovakis cardinal--some combinatorial property related to determinacy?--and I couldn't find anything by startpaging or duckduckgoing.
