This thesis is concerned with algorithmic investigations in p-adically closed fields, of which Hensel's field of p-adic numbers is prototypical. The well known analogies between the field of real numbers and the field of p-adic numbers are supplemented from a computational standpoint. We resolve the complexity of the Decision Problem for Fields in the p-adic case. We work in the new $n$th power formalism for p-adic fields where the correspondence to the reals is most transparent. First we give an alternating exponential time algorithm for deciding linear sentences in the theory of p-adically closed fields. This also translates into a deterministic algorithm running in exponential space or double exponential time. A deterministic quantifier-elimination procedure for the linear fragment running in double exponential time and space is also presented. Next we employ a quantitative version of a Cell Decomposition Lemma due to Denef to give an alternating exponential time decision procedure for the full theory. As usual this also yields a deterministic decision procedure running in double exponential time or in exponential space, and a quantifier elimination procedure running in double exponential time and space. These complexity bounds are demonstrated to be essentially optimal by proving matching lower bounds on the respective problems. We give a simple algorithm to determine all roots among the p-adic integers of a given polynomial equation. This algorithm is a purely symbolic (as opposed to numerical) p-adic version of the classical Newton and Horner iteration methods and has a natural parallel implementation. We also give algorithms for some problems in valued fields and in p-adic semi-algebraic geometry. Finally we give some additional elementary evidence to support the thesis that certain cosets of $n$th powers are the proper p-adic analogues to signs in the real case. This is done by showing that these coset representatives display similar behavior with respect to functions and their derivatives, as do the signs in the real case.