A method for distributed tokenization of sensitive strings of characters, such as social security numbers, credit card numbers and the like, in a local server is disclosed. The method comprises the steps of receiving from a central server at least one, and preferably at least two, static token lookup tables, and receiving a sensitive string of characters. In a first tokenization step, a first substring of characters is substituted with a corresponding first token from the token lookup table(s) to form a first tokenized string of characters, wherein the first substring of characters is a substring of the sensitive string of characters. Thereafter, in a second step of tokenization, a second substring of characters is substituted with a corresponding second token from the token lookup table(s) to form a second tokenized string of characters, wherein the second substring of characters is a substring of the first tokenized string of characters. Optionally, one or more additional tokenization steps is/are used.