Given the Lagrangian $L$ for a system, we can construct the Hamiltonian $H$ using the definition $H=\sum\limits_{i}p_i\dot{q}_i-L$ where $p_i=\frac{\partial L}{\partial \dot{q}_i}$. Therefore, to determine, $p_i$ we need to know $L$.
Now suppose, we are given the Hamiltonian $H$. Can we then reconstruct the Lagrangian $L$? Certainly the relation $L=\sum\limits_{i}p_i\dot{q}_i-H$ is not helpful because there is no prescription how to determine $p_i$ without knowing $L$.
Yes, there exists a Legendre transformation from $g(p)$ to $f(x)$: $$ f(x)=p(x)x-g(p(x)) $$ with $x=dg/dp$. Here the notation $p(x)$ means $p$ written in terms of $x$. In your case, the Hamiltonian is a function of $p$ and you are transforming it to a function of $\dot{q}$, so you must use Hamilton's equation to get the velocity: $$ \dot{q}_i=\frac{\partial H}{\partial p_i} $$ which you then solve for $p$ (so that it's a function of $\dot{q}$, e.g. $p=h(\dot{q})$). You then have your Lagrangian as $$ L(q,\dot{q})=\dot{q}_ih(\dot{q}_i)-H(q,h(\dot{q})) $$
For the (relativistic) Hamiltonian1, $$ H(q,p)=\sqrt{p^2c^2+m^2c^4}+V(q) $$ the momentum should be $$ p(\dot{q})=\frac{m\dot{q}}{\sqrt{1-\dot{q}^2/c^2}} $$ which was computed using $\dot{q}=\partial H/\partial p$ & then inverting to get $p$ in terms of $\dot{q}$. You should verify that this is correct (but it does look right to the relativistic momentum, $p=\gamma mv$). Then you can just do the substitution and get your Lagrangian.
1. This particular Hamiltonian was included in version 2 of this question, but was since removed; as it still provides an example of the $H\to L$ transform, I kept it in.
First of all, the hamiltonian contains the coordinates $q_i$ and their momenta $p_i$. You have to calculate the velocities $\dot{q}_i$. For that, you'll need the Hamilton-Jacobi equations $$\dot{q}_i = \frac{\partial H}{\partial p_i}$$The Legendre transform, as noted in the comments, is involutive, so the lagrangian is just the Legendre transform of the hamiltonian $$L = \sum_i p_i \dot{q}_i - H$$ where you have to express everywhere the momenta in terms of the velocities.
Worked-out example: harmonic oscillator. The well-known hamiltonian is $$H = \frac{p^2}{2m} + \frac{1}{2}m\omega^2 q^2$$ From the Hamilton-Jacobi we get (unsurprisingly) that $$\dot{q} = \frac{\partial H}{\partial p} = \frac{p}{m}$$ And plug it in the Legendre transform $$L = \dot{q}p - H = \dot{q}(\dot{q} m) - \frac{(\dot{q}m)^2}{2m} - \frac{1}{2}m\omega^2 q^2 = \frac{1}{2}m \dot{q}^2 - \frac{1}{2}m\omega^2 q^2$$Which is indeed the lagrangian for the harmonic oscillator.
Let us suppress explicit time dependence $t$ from the notation in the following. Hamilton's eqs. are the Euler-Lagrange (EL) eqs. for the so-called Hamiltonian Lagrangian
$$\tag{1} L_H(q,\dot{q},p)~:=~ p_i\dot{q}^i-H(q,p).$$
In other words, the solutions to Hamilton's eqs. are stationary points for the Hamiltonian action
$$\tag{2} S_H[q,p]~:=~\int \! dt~L_H(q,\dot{q},p). $$
Next define the Lagrangian as
$$ \tag{3} L(q,\dot{q})~:=~\sup_p L_H(q,\dot{q},p). $$
Formula (3) is the succinct answer to OP's question about how to construct the Lagrangian from the Hamiltonian.
The Legendre transformation (3) is often referred to as integrating out$^1$ the momentum variables $p_i$. Then the action (2) becomes
$$ \tag{4} S[q]~:=~\int \! dt~L(q,\dot{q}). $$
The stationary points of the action (4) are given by the EL eqs. for $L$.
--
$^1$ If we go beyond classical mechanics, and consider the phase space path integral formulation, then "integrating out the momentum" is exactly what is happening.
