Let $K$ be a field, and let $\alpha$ be transcendental over $K$ and algebraic over $K(\beta)$. We have a Hasse diagram of field extensions
diag http://i.picresize.com/images/2015/06/23/nHsFx.jpg
Now, by reduction to absurdity $\beta$ must be transcendental over $K$ as well (this is asked but I'm not sure if it's relevant to the question). The problem is to prove that $\beta$ must be algebraic over $K(\alpha)$.
The first thing I tried is to take whatever polynomial annihilates $\alpha$: $$a_0 + a_1\alpha\cdots + a_n\alpha^n = 0$$ with $a_0,\dots,a_n\in K(\beta)$. If $\beta$ were algebraic over $K$, then I could rewrite this as $$\sum\nolimits_1^m\lambda_{i,0}\beta^i + \left(\sum\nolimits_1^m\lambda_{i,1}\beta^i\right)\alpha + \cdots + \left(\sum\nolimits_1^m\lambda_{i,n}\beta^i\right)\alpha^n$$ And this would of course give a polynomial that annihilates $\beta$ with coefficients in $K(\alpha)$ (aside from the fact that $K(\alpha,\beta)/K(\alpha)$ would be algebraic by mulitplicity of degree). The thing is, when it comes to transcendental extensions, I'm just not sure that $$\left\{\beta^k\right\}_{k\in\Bbb N}$$ is still a $K$-basis for $K(\beta)$. If this were true then I suppose my question is how to prove this. If not, what other method might I try?
I also wonder whether or not this is a special case of $$E,L\supset K \,\wedge\, F/E \text{ algebraic }\stackrel ?\implies F/L\text{ algebraic }$$ My guess is no, but I also can't think of an counterexample because I only know of simple transcendental extensions (where it would be true by what I originally wanted to prove).
My comment essentially says it all, so let me use the answer space to give a more philosophical answer.
Fields are wonderful little worlds. There are a ton of axioms that go into their definition, but that is compensated by the tons of structure that lie within them. In thinking about a field $K(\beta)$, these structures give rise to several ways of understanding $K(\beta)$ that are each useful in different contexts.
If $\beta$ is an element of a known extension field $E$ of $K$, then $K(\beta)$ is the intersection of all subfields of $E$ containing $K$.
From the point of view of the vector space structure, as you observe, if $K(\beta)$ is finite-dimensional over $K$, then one can find some list of powers $1, \beta, \beta^2, \ldots, \beta^n$ that form a $K$-basis of $K(\beta)$. This happens precisely when $\beta$ is algebraic over $K$. This point of view is more convenient than (1) if you want to write down a useful form for elements of $K(\beta)$. Here, you can write them as linear combinations on the basis. This is less useful when you need an infinite basis, i.e., the transcendental case.
Even more concretely, you can think of elements of $K(\beta)$ as all elements you can reach by performing a finitely list of field operations using elements of $K$ and $\beta$, i.e.
$a + \frac{1}{\beta}$ or $\frac{\beta^2 + 2\beta}{\beta^3 + a_1\beta + a_2}$
where $a$, $a_1$, and $a_2$ are elements of $K$ and the `2' just means add to itself. You should be able to convince yourself that every such expression can be written as a quotient of polynomials in $\beta$ with coefficients in $K$. You should also try to prove the equality of the set of such elements with the set described in point of view (1).
Now consider when $\beta$ is algebraic and compare points of view (2) and (3). We see that the expressions in (2) are just quotients as in (3) but with denominator 1. So we see the surprising result that ever quotient of polynomials in $\beta$ actually equals a polynomial in $\beta$ when $\beta$ is algebraic. This is not true when $\beta$ is transcendental.
Thus, (2) is the typical point of view when $\beta$ is algebraic, while (3) is when $\beta$ is transcendental and is the form of expression I put in the comment.