There is nothing async about your function, it is entirely CPU bound work. Changing the signature to async Task<LevenshteinMatches> and never using await in the function should have caused a warning in the compiler.
Instead of "making it async" if the thing you are really after is making it work in parallel then just call the code in parallel.
string s = "xcjavxzcbvmrmummuuutmtumuumtryumtryumtrutryumtryumtrymutryumtyumtryumtrmutyumtrurtmutymurtmyutrymut"; s = string.Concat(Enumerable.Repeat(s, 4000)); var expressions = new[] {"jas", "cbv"} var tasks = new List<Task<LevenshteinMatches>>() foreach(var expression in expressions) { var task = new Task.Run(()=> message.LevenshteinSingleThread(expression, 1)); //Start multiple threads tasks.Add(task); } LevenshteinMatches[] results = Task.WaitAll(tasks); //Wait for all the threads to end. You could even make parts of the internal function multi-threaded by using Parallel.For( to make some of the for loops parallel, just be careful that any collections you call Add on are either synchronized inside a lock or are thread safe collections.